package com.LeeCode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 表现良好的最长时间段
 */

public class Code1124 {
    public static void main(String[] args) {
        int[] hours = {9, 9, 6, 0, 6, 6, 9};
        System.out.println(new Code1124().longestWPI(hours));
    }

    public int longestWPI(int[] hours) {
        int n = hours.length;
        int[] preSum = new int[n + 1];
        // 计算前缀和数组
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + (hours[i] > 8 ? 1 : -1);
        }

        // 使用单调栈存储前缀和的索引，保持递减
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            if (stack.isEmpty() || preSum[stack.peek()] > preSum[i]) {
                stack.push(i);
            }
        }

        // 从右到左遍历，寻找最大长度
        int maxLen = 0;
        for (int i = n; i >= 0; i--) {
            while (!stack.isEmpty() && preSum[stack.peek()] < preSum[i]) {
                maxLen = Math.max(maxLen, i - stack.pop());
            }
        }
        return maxLen;
    }

    public int longestWPI1(int[] hours) {
        int maxLen = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < hours.length; i++) {
            sum += hours[i] > 8 ? 1 : -1;

            if (sum > 0) {
                // 前缀和大于0，整个数组到当前位置都满足条件
                maxLen = i + 1;
            } else {
                // 寻找是否存在前缀和为sum-1的位置
                // 因为这样当前子数组的和就是sum-(sum-1)=1>0
                if (map.containsKey(sum - 1)) {
                    maxLen = Math.max(maxLen, i - map.get(sum - 1));
                }
            }

            // 只记录第一次出现该前缀和的位置
            map.putIfAbsent(sum, i);
        }

        return maxLen;
    }
}
